import { ConvexPolyhedron } from "./ConvexPolyhedron";
import { Plane } from "./Plane";
import { Vector3 } from "./Vector3";
import { TriIndex } from "./IndexTriangle";
import { MathUtil } from "./MathUtil";

/**
 * 辅助结构体，顶点。
 */
class ConvVertex {
    //值。
    public point: Vector3;
    //距离。
    public distance: number;
    //
    public occurs: number;
    //可见性。
    public visible: boolean;
    public constructor() {
        //        this.point = new Vector3();
        this.distance = 0.0;
        this.visible = true;
    }
}

/**
 * 辅助结构体，边。
 */
class ConvEdge {
    public vertex: number[] = [2];//2
    public face: number[] = [2];//2
    public visible: boolean;
    public constructor() {
        this.visible = true;
    }
}

/**
 * 辅助结构体，面。
 */
class ConvFace {
    public plane: any;
    //ts的集合不对元素排序，只好用array代替。
    public edges: Array<number>;
    public visible: boolean;
    public constructor() {
        this.edges = new Array<number>();
        this.visible = true;
    }

    /**
     * 移除一条边。
     * 
     * @param edge 边索引
     */
    public removeEdge(edge: number): void {
        for (var e = 0; e < this.edges.length; e++) {
            var index = this.edges.indexOf(edge);
            if (index > -1) {
                this.edges.splice(index, 1);
                break;
            }
        }
    }
}

/**
 * 辅助结构体，增量边。
 */
class EdgePlus {
    public e: number;
    public v0: number;
    public v1: number;
    public f0: number;
    public f1: number;

    /**
     * 构造函数。
     * @param e 边索引。
     * @param edge 边。
     */
    public constructor(e?: number, edge?: ConvEdge) {
        this.e = e ? e : -1;
        if (edge != null) {
            this.f0 = edge.face[0];
            this.f1 = edge.face[1];
            if (edge.vertex[0] < edge.vertex[1]) {
                this.v0 = edge.vertex[0];
                this.v1 = edge.vertex[1];
            } else {
                this.v0 = edge.vertex[1];
                this.v1 = edge.vertex[0];
            }
        }
    }

    /**
     * 深拷贝。
     * 
     * @param edge
     */
    public copy(edge: EdgePlus) {
        this.e = edge.e;
        this.v0 = edge.v0;
        this.v1 = edge.v1;
        this.f0 = edge.f0;
        this.f1 = edge.f1;
    }

    /**
     * 是否小于。
     * 
     * @param ep 
     */
    public lessThan(ep: EdgePlus): boolean {
        if (this.v1 < ep.v1) return true;
        if (this.v1 === ep.v1) return this.v0 < ep.v1;
        return false;
    }

    /**
     * 是否相等。
     * 
     * @param ep 
     */
    public equals(ep: EdgePlus): boolean {
        return (this.v0 === ep.v0) && (this.v1 === ep.v1);
    }

    /**
     * 是否不等。
     * @param ep 
     */
    public unequals(ep: EdgePlus): boolean {
        return !this.equals(ep);
    }
}

/**
 * 凸多面体分割类。 
 * 
 */
export class ConvexClipper {
    //公差。
    public static tolerance = 1.0E-6;
    //点集。
    public vertices: Array<ConvVertex>;
    //边集。
    public edges: Array<ConvEdge>;
    //面集。
    public faces: Array<ConvFace>;

    /**
     * 构造函数。
     */
    public constructor() {
        //  this.vertices = new Array<ConvVertex>();
        //  this.edges = new Array<ConvEdge>();
        //   this.faces = new Array<ConvFace>();
    }

    /**
     * 设置被裁减多面体。
     * @param convex 多面体。
     */
    public setClippedConvexPolyhedron(convex: ConvexPolyhedron): void {
        // 顶点。
        var numVertices = convex.vertices.length;
        var points = convex.points;
        this.vertices = new Array<ConvVertex>(numVertices);
        for (var v = 0; v < numVertices; v++) {
            var vertex = this.vertices[v] = new ConvVertex();
            //这里做引用即可。
            vertex.point = points[v];
        }
        // 边。
        var numEdges = convex.edges.length;
        this.edges = new Array<ConvEdge>(numEdges);
        for (var e = 0; e < numEdges; e++) {
            var edge = convex.edges.get(e);
            var thed = this.edges[e] = new ConvEdge();
            for (var i = 0; i < 2; i++) {
                var v = edge.vertex[i];
                thed.vertex[i] = convex.getVertexLabel(v);
                thed.face[i] = edge.triangle[i];
            }
        }
        // 面。
        var numTris = convex.triangles.length;
        this.faces = new Array<ConvFace>(numTris);
        for (var t = 0; t < numTris; t++) {
            var face = this.faces[t] = new ConvFace();
            face.plane = convex.planes[t];
            var tri = convex.triangles.get(t);
            for (var i = 0; i < 3; i++) {
                var e = tri.edge[i];
                face.edges.push(e);
            }
            var esort = function (a, b): number {
                if (a > b) return 1;
                if (a == b) return 0;
                if (a < b) return -1;
            };
            face.edges.sort(esort);
        }
    }

    /**
     * 后期处理。
     * @param fNew
     * @param faceNew 
     */
    public postprocess(fNew: number, faceNew: ConvFace) {
        //lambda
        var esort = function (ep0: EdgePlus, ep1: EdgePlus): number {
            if (ep0.lessThan(ep1)) return 1;
            if (ep1.equals(ep1)) return 0;
            return -1;
        };
        //
        var numEdges = faceNew.edges.length;
        var edges = new Array<EdgePlus>();
        faceNew.edges.forEach((e0, e1, set) => {
            var edge = this.edges[e0];
            var ep = new EdgePlus(e0, edge);
            edges.push(ep);
        });
        //   edges.sort(esort);//这个地方有可能出错。
        //冒泡排序
        var swap = function (e0, e1) {
            var temp = new EdgePlus();
            temp.copy(e0);
            e0.copy(e1);
            e1.copy(temp);
        };
        for (var i = 0; i < edges.length - 1; i++) {
            var ee0 = edges[i];
            for (var j = i + 1; j < edges.length; j++) {
                var ee1 = edges[j];
                if (ee1.lessThan(ee0)) {
                    swap(edges[i], edges[j]);
                }
            }
        }

        //
        for (var i0 = 0, i1 = 1; i1 < numEdges; i0 = i1++) {
            if (edges[i0].equals(edges[i1])) {
                var e0 = edges[i0].e;
                var e1 = edges[i1].e;
                var edge0 = this.edges[e0];
                var edge1 = this.edges[e1];
                faceNew.removeEdge(e0);
                faceNew.removeEdge(e1);
                //
                if (edge0.face[0] === fNew) {
                    edge0.face[0] = edge0.face[1];
                } else {
                    //未知错误。
                    //      AssertUtil.debugTrue(false);
                }
                edge0.face[1] = -1;
                //
                if (edge1.face[0] === fNew) {
                    edge1.face[0] = edge1.face[1];
                } else {
                    //       AssertUtil.debugTrue(false);
                }
                edge1.face[1] = -1;
                //
                var f1 = edge1.face[0];
                var face1 = this.faces[f1];
                face1.removeEdge(e1);
                face1.removeEdge(e0);
                edge0.face[1] = f1;
                edge1.visible = false;
            }
        }
    }

    /**
     * 获取开放多线。
     * @param ret 存放结果。
     */
    public getOpenPolyline(face: ConvFace): { vstart: number; vfinal: number } {
        var okey = true;
        var len = face.edges.length;
        var vstart: number = -1 | 0;
        var vfinal: number = -1 | 0;
        //
        for (var e of face.edges) {
            var edge = this.edges[e];
            var v0 = edge.vertex[0];
            var occ = ++this.vertices[v0].occurs;
            if (occ > 2) {
                okey = false;
            }
            var v1 = edge.vertex[1];
            occ = ++this.vertices[v1].occurs;
            if (occ > 2) {
                okey = false;
            }
        }
        //
        if (!okey) {
            // 如果定位到这里，可能发生未知错误。
            // AssertUtil.debugFalse(true);
        }
        //
        for (var e of face.edges) {
            var edge = this.edges[e];
            var v0 = edge.vertex[0];
            if (this.vertices[v0].occurs == 1) {
                if (vstart == -1) {
                    vstart = v0;
                }
                else if (vfinal == -1) {
                    vfinal = v0;
                }
            }
            //
            var v1 = edge.vertex[1];
            if (this.vertices[v1].occurs == 1) {
                if (vstart == -1) {
                    vstart = v1;
                } else if (vfinal == -1) {
                    vfinal = v1;
                }
            }
        }
        return vstart === -1 ? null : { vstart, vfinal };
    }

    /**
     * 用一个平面切割。
     * @param plane
     */
    public clip(plane: Plane): number {
        var numPositive = 0 | 0, numNegative = 0 | 0, numZero = 0 | 0;
        var numVertices = this.vertices.length;
        for (var i = 0; i < numVertices; i++) {
            var vertex = this.vertices[i];
            if (vertex.visible) {
                vertex.distance = plane.distanceToPoint_v2(vertex.point);
                if (vertex.distance > ConvexClipper.tolerance) {
                    ++numPositive;
                } else if (vertex.distance < -ConvexClipper.tolerance) {
                    ++numNegative;
                    vertex.visible = false;
                } else {
                    ++numZero;
                    vertex.distance = 0;
                }
            }
        }
        //网格在负半空间里。
        if (numPositive === 0) {
            return -1;
        }
        //网格在正半空间里。
        if (numNegative === 0) {
            return 1;
        }
        //穿过多面体。
        var numEdges = this.edges.length;
        for (var e = 0; e < numEdges; e++) {
            var edge = this.edges[e];
            if (edge.visible) {
                var v0 = edge.vertex[0];
                var v1 = edge.vertex[1];
                var f0 = edge.face[0];
                var f1 = edge.face[1];
                var face0 = this.faces[f0];
                var face1 = this.faces[f1];
                var d0 = this.vertices[v0].distance;
                var d1 = this.vertices[v1].distance;
                if (d0 <= ConvexClipper.tolerance && d1 <= ConvexClipper.tolerance) {
                    //边缘被剔除。如果边缘恰好在剪辑平面上，可能有一个可见的三角形与之共享。
                    //边缘将在face loop过程中重新添加。
                    face0.removeEdge(e);
                    if (face0.edges.length == 0) {
                        face0.visible = false;
                    }
                    face1.removeEdge(e);
                    if (face1.edges.length == 0) {
                        face1.visible = false;
                    }
                    edge.visible = false;
                    continue;
                }
                //边在平面上。
                if (d0 >= ConvexClipper.tolerance && d1 >= ConvexClipper.tolerance) {
                    continue;
                }
                //边已经被平面打断，计算相交点。如果旧边是<V0,V1>并且I为交点，当d0>0时，
                //新边为<V0,I>，当d1>0时，新边为<I,V1>。
                var vNew = this.vertices.length;
                var vertNew = new ConvVertex();
                this.vertices.push(vertNew);
               // var vertNew = this.vertices[vNew];
                var pt0 = this.vertices[v0].point;
                var pt1 = this.vertices[v1].point;
                var d = d0 / (d0 - d1);
                var pt = Vector3.sub(pt1, pt0);
                pt.multiplyScalar(d);
                vertNew.point = pt.add(pt0);
                //
                if (d0 > 0.0) {
                    edge.vertex[1] = vNew;
                } else {
                    edge.vertex[0] = vNew;
                }
            }
        }

        //
        var fNew = this.faces.length;
        this.faces.push(new ConvFace());
        var faceNew = this.faces[fNew];
        faceNew.plane = plane;
        //
        for (var f = 0; f < fNew; f++) {
            var face = this.faces[f];
            if (face.visible) {
                var size = face.edges.length;
                for (var e of face.edges) {
                    var edge = this.edges[e];
                    var v0 = edge.vertex[0];
                    var v1 = edge.vertex[1];
                    this.vertices[v0].occurs = 0;
                    this.vertices[v1].occurs = 0;
                }
                //
                var ret = this.getOpenPolyline(face);
                if (ret != null) {
                    var eNew = this.edges.length;
                    this.edges.push(new ConvEdge());
                    var edgeNew = this.edges[eNew];
                    edgeNew.vertex[0] = ret.vstart;
                    edgeNew.vertex[1] = ret.vfinal;
                    edgeNew.face[0] = f;
                    edgeNew.face[1] = fNew;
                    //add new edges to polygon
                    face.edges.push(eNew);
                    faceNew.edges.push(eNew);
                }
            }
        }
        //
        this.postprocess(fNew, faceNew);
        if (faceNew.edges.length < 3) {
            this.faces.pop();
        }
        return 0;
    }

    /**
     * 转换成凸多面体。
     */
    public toPolyhedron(): ConvexPolyhedron {
        var numVertices = this.vertices.length;
        var points = new Array<Vector3>();
        var vmap = new Array<number>(numVertices);
        vmap.fill(0xFF);
        for (var v = 0; v < numVertices; v++) {
            var vertex = this.vertices[v];
            if (vertex.visible) {
                vmap[v] = points.length;
                points.push(vertex.point);
            }
        }
        //
        var param = this.getTriangles();
        //
        var length = param.indices.length;
        for (var i = 0; i < length; i++) {
            var oldt = param.indices[i];
            //     AssertUtil.debugTrue(0 <= oldc && oldc < numVertices);
            var newt = vmap[oldt];
            //     AssertUtil.debugTrue(0 <= newc && newc < points.length);
            param.indices[i] = newt;
        }
        //make triangles
        var numTri = length / 3;
        var triangles = new Array<TriIndex>(numTri);
        for (var t = 0; t < numTri; t++) {
            var a = param.indices[t * 3 + 0];
            var b = param.indices[t * 3 + 1];
            var c = param.indices[t * 3 + 2];
            triangles[t] = new TriIndex(a, b, c);
        }
       //   ConvexClipper.print(points, triangles, param.planes);
        var values = ConvexPolyhedron.redundancyEliminatted(points, triangles);
        var convex = new ConvexPolyhedron();
        convex.setValue(values.newPoints, values.newTriangles);
   //     convex.create(points, triangles, param.planes);
        return convex;
    }

    /**
     * 
     * @param points
     * @param indices
     * @param planes
     */
    public static print(points: Array<Vector3>,
        indices: Array<TriIndex>, planes: Array<Plane>) {
        //
        var numPoints = points.length;
        var text = "points: " + numPoints + "\n";
        for (var p = 0; p < numPoints; p++) {
            var vertex = points[p];
            text += "point <" + p + "> = (" + vertex.x.toFixed(4) +
                "," + vertex.y.toFixed(4) + "," + vertex.z.toFixed(4) + ")\n";
        }
        text += "\n";

        //triangles
        var numTriangles = indices.length;
        text += "triangles: " + numTriangles + "\n";
        for (var t = 0; t < numTriangles; t++) {
            var tri = indices[t];
            text += "triangle<" + t + "> = (" +
                tri.a + "," + tri.b + "," + tri.c + ")\n";
        }
        text += "\n";

        //planes
        text += "planes:\n";
        var numPlanes = planes.length;
        for (var p = 0; p < numPlanes; p++) {
            var plane = planes[p];
            text += "plane<" + p + "> = (" + plane.normal.x.toFixed(6) +
                "," + plane.normal.y.toFixed(6) + "," + plane.normal.z.toFixed(6) +
                "," + plane.constant.toFixed(4) + ")\n";
        }
        text += "\n";

        var fs = require("fs");
        fs.writeFileSync("D:\\test\\convex\\middle_ts.txt", text);
        return text;
    }

    /**
     * 
     * @return indices 三角面索引集。
     * @return planes 平面集。
     */
    public getTriangles(): { indices: Array<number>, planes: Array<Plane> } {
        var indices = new Array<number>();
        var planes = new Array<Plane>();
        //lambda
        var push = function (i, j, plane) {
            indices.push(v0);
            indices.push(vordered[i]);
            indices.push(vordered[j]);
            planes.push(plane);
        };

        var numFaces = this.faces.length;
        for (var f = 0; f < numFaces; f++) {
            var face = this.faces[f];
            if (face.visible) {
                var numEdges = face.edges.length;
                // AssertUtil.debugTrue(numEdges >= 3);
                var vordered = this.orderVertices(face);
                var v0 = vordered[0];
                var v2 = vordered[numEdges - 1];
                var vv = Math.floor(numEdges / 2.0) | 0;
                var v1 = vordered[vv];
                var pt0 = this.vertices[v0].point;
                var pt1 = this.vertices[v1].point;
                var pt2 = this.vertices[v2].point;
                var diff1 = Vector3.sub(pt1, pt0);
                var diff2 = Vector3.sub(pt2, pt0);
                var crs = diff1.cross(diff2);
                var sgn = face.plane.normal.dot(crs);

                if (sgn > 0.0) {
                    // 顺时针，需要翻转。
                    for (var i = 1; i + 1 < numEdges; i++) {
                        push(i + 1, i, face.plane);
                    }
                } else {
                    // 逆时针.
                    for (var i = 1; i + 1 < numEdges; i++) {
                        push(i, i + 1, face.plane);
                    }
                }
            }
        }
        return { indices, planes };
    }

    /**
     * 排列顶点集。
     * 
     * @param face
     */
    public orderVertices(face: ConvFace): Array<number> {
        var numEdges = face.edges.length;
        var eordered = new Array<number>();
        var vordered = Array<number>();
        //
        face.edges.forEach((e0) => {
            eordered.push(e0);
        });

        //lambda
        var swap = function (i, j) {
            var temp = eordered[i];
            eordered[i] = eordered[j];
            eordered[j] = temp;

        };
        // 冒泡排序（可优化）
        var i0 = 0, i1 = 1, choice = 1;
        for (; i1 < numEdges - 1; i0 = i1++) {
            var e = eordered[i0];
            var curEdge = this.edges[e];
            var curr = curEdge.vertex[choice];
            for (var j = i1; j < numEdges; j++) {
                e = eordered[j];
                var tempEdge = this.edges[e];
                if (tempEdge.vertex[0] == curr) {
                    swap(i1, j);
                    choice = 1;
                    break;
                }
                if (tempEdge.vertex[1] == curr) {
                    swap(j, i1);
                    choice = 0;
                    break;
                }
            }
        }

        var idx = eordered[0];
        vordered[0] = this.edges[idx].vertex[0];
        vordered[1] = this.edges[idx].vertex[1];
        for (var i = 0; i < numEdges; i++) {
            idx = eordered[i];
            var edge = this.edges[idx];
            if (edge.vertex[0] == vordered[i]) {
                vordered[i + 1] = edge.vertex[1];
            }
            else {
                vordered[i + 1] = edge.vertex[0];
            }
        }

        return vordered;
    }

    /**
     * 把内容转换成字符串，调试用。 
     */
    public print(): string {
        var text: string;
        var numVertices = this.vertices.length;
        var numEdges = this.edges.length;
        var numFaces = this.faces.length;

        text = numVertices + ' vertices\n';
        for (var v = 0; v < numVertices; v++) {
            var vertex = this.vertices[v];
            text += 'v<' + v + '> ' + (vertex.visible ? 'T' : 'F') + ': (' +
                vertex.point.x + ',' + vertex.point.y + ',' + vertex.point.z + ')\n';
        }
        text += '\n';

        text += numEdges + ' edges\n';
        for (var e = 0; e < numEdges; e++) {
            var edge = this.edges[e];
            text += 'e<' + e + '>' + (edge.visible ? 'T' : 'F') + ': v[' +
                edge.vertex[0] + ',' + edge.vertex[1] + '], ' + 't[' +
                edge.face[0] + ',' + edge.face[1] + ']\n';
        }
        text += '\n';

        text += numFaces + ' numFaces\n';
        for (var f = 0; f < numFaces; f++) {
            var face = this.faces[f];
            text += 't<' + f + '>' + (face.visible ? 'T' : 'F') + ': e =';
            for (var e of face.edges.values()) {
                text += e + ' ';
            }
            text += '\n';
        }

        return text;
    }

    /**
     * 保存到文件。
     */
    public save(filepath: string): void {
        var text = this.print();
        var fs = require("fs");
        fs.writeFileSync(filepath, text);
    }
}